package practice18;

public class Main {
    public static int solution(String dna1, String dna2) {
        int len1 = dna1.length();
        int len2 = dna2.length();
        
        // 创建一个二维数组来存储子问题的解
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        // 初始化边界条件
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i; // 将dna1转换为空串所需的操作数
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j; // 将空串转换为dna2所需的操作数
        }
        
        // 填充dp表
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (dna1.charAt(i - 1) == dna2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // 如果字符相同，则不需要额外操作
                } else {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                    // 分别对应删除、插入和替换操作
                }
            }
        }
        
        return dp[len1][len2]; // 返回最终的编辑距离
    }

    public static void main(String[] args) {
        // 测试案例
        System.out.println(solution("AGT", "AGCT")); // 输出: 1
        System.out.println(solution("AACCGGTT", "AACCTTGG")); // 输出: 4
        System.out.println(solution("ACGT", "TGC")); // 输出: 3
        System.out.println(solution("A", "T")); // 输出: 1
        System.out.println(solution("GGGG", "TTTT")); // 输出: 4
        System.out.println(solution("AGCTTAGC", "AGCTAGCT")); // 输出: 2
        System.out.println(solution("AGCCGAGC", "GCTAGCT")); // 输出: 4
    }
}